/****************************************************************
malloc.c
****************************************************************/

#define DEBUG 1					//DO NOT REMOVE THIS LINE
						//UNTIL OUT OF BETA CYCLE
						//THIS KEEPS CHECKS AND BALANCES
						//INSIDE MALLOC AND FREE

#include <string.h>
#include <stdlib.h>
#ifdef DEBUG
	#include "macros.h"	//ONLY include if debug is enabled.
#else
	#define assert {}
#endif

// ** structs ** //
struct head
{
	long prev;
	long size;
};
#define HEAD(p) ((struct head *)(p))

struct links
{
	struct freehead *forward;
	struct freehead *backward;
};

struct freehead
{
	struct head h;
	struct links l;
};
#define FREE(p) ((struct freehead *)(p))

struct directhead
{
	long tsize;
	struct head h;
};
#define DIRECT(p) ((struct directhead *)(p))

static struct freehead kfreelist = {
	{0, 0},
	{&kfreelist, &kfreelist}
};

static long ktotal_alloc = 0;		//total space currently allocated to kernel
static long knumalloc = 0, knumfree = 0;//number of calls to kmalloc/kfree
static long ktotal_memory = 0;		//total amount of memory available to kmalloc

// End sentinel: this is the value that is placed in a dummy block
// placed at the end of the pool.
#define EndS	((long) (-(((1L << (sizeof(size_t) * 8 - 2)) - 1) * 2) - 2))
// 0x80000000 on x86

void *kmalloc(long request)
{
	long size = request;
	
	struct freehead *h;
	void *buf;
	
	assert(size > 0);
	
	if(size < (sizeof(struct links)))
	{
		size += (sizeof(struct links));
	}
	
	size += sizeof(struct head);	//overhead
	
	h = kfreelist.l.forward;
	
	while(h != &kfreelist)
	{
		if((size_t)h->h.size >= size)
		{
			/* current buffer is big enough to allocate
			   now decide if we can split it or not */
			if((h->h.size - size) > (sizeof(struct freehead)))
			{
				struct freehead *a;
				struct head *next;
				
				a = FREE(((char *)h) + (h->h.size - size));	//*a = *h + size
				next = HEAD(((char *)a) + size);		//*next = *a + size
				assert(next->prev == h->h.size);//make sure this is correct
				h->h.size -= size;		//decrement/split from h
				a->h.prev = h->h.size;		//previous free block = h
				a->h.size = -(size_t) size;	//negate size to mark allocated
				a->l.forward = h->l.forward;	//correct...
				a->l.backward = h;		//...placement
				next->prev = 0;			//next buffer not proceeded by free
				ktotal_alloc += size;		//add the size to total memory usage
				knumalloc++;			//# of times malloc() has been called
				buf = (void *) ((((char *)a) + sizeof(struct head)));
				printf("\nif==true");
				KiDumpFreeStruct(h);
				printf("buf == %08X, a == %08X. h == %08X\n", buf, a, h);
				
				return buf;
			} else {
				struct head *a;
				
				a = HEAD(((char *)h) + h->h.size);		//*a = *h + size
				assert(h->l.backward->l.forward == h);		//ensure correct...
				assert(h->l.forward->l.backward == h);		//...placement
				h->l.backward->l.forward = h->l.forward;	//remove from freelist
				h->l.forward->l.backward = h->l.backward;	//remove from freelist
				ktotal_alloc += h->h.size;	//add the size to total memory usage
				knumalloc++;			//# of times malloc() has been called
				h->h.size = -(h->h.size);	//negate size to mark allocated
				a->prev = 0;			//next buffer not proceeded by free
				printf("\nif==false");
				KiDumpFreeStruct(h);
				
				buf = (void *) &(h->l);
				return buf;;
			}
		}
		h = h->l.forward;
	}
	
	return NULL;	//oops, no memory available
			//TODO: errno = ENOMEM;
}

void kfree(void *tofree)
{
	struct freehead *f, *next;
	
	dprintf("1");
	f = FREE(((char *)tofree) - sizeof(struct head));
#ifdef DEBUG
	KiDumpFreeStruct(f);
#endif
	dprintf("2");
	knumfree++;
	dprintf("3");
	if(tofree == NULL)
		return;
		
	dprintf("4");
	if(f->h.size >= 0)
		next = NULL;
		
	dprintf("5");
	assert(f->h.size < 0);
	
	dprintf("6");
	assert(f->l.forward->h.prev == 0);
	dprintf("7");
	ktotal_alloc += f->h.size;
	dprintf("8");
	assert(ktotal_alloc >= 0);
	dprintf("9");
	if(f->h.prev != 0)		//previous buffer is free
	{
		register long size = f->h.size;
		
		dprintf("10");
		assert(HEAD((char *)f - f->h.prev)->size == f->h.prev);
		dprintf("11");
		f = FREE(((char *)f) - f->h.prev);
		dprintf("12");
		f->h.size -= size;
		dprintf("13");
	} else {			//previous buffer is not free
		dprintf("14");
		assert(kfreelist.l.backward->l.forward == &kfreelist);
		dprintf("15");
		assert(kfreelist.l.forward->l.backward == &kfreelist);
		dprintf("16");
		f->l.forward = &kfreelist;
		dprintf("17");
		f->l.backward = kfreelist.l.backward;
		dprintf("18");
		kfreelist.l.backward = f;
		dprintf("19");
		f->l.backward->l.forward = f;
		dprintf("20");
		f->h.size = -(f->h.size);
		dprintf("21");
	}
	
	//see if next buffer is free
	dprintf("22");
	next = FREE(((char *)f) + f->h.size);
	dprintf("23");
	if(next->h.size > 0)
	{
		dprintf("24");
		assert(HEAD((char *)next + next->h.size)->prev == next->h.size);
		dprintf("25");
		assert(next->l.backward->l.forward == next);
		dprintf("26");
		assert(next->l.forward->l.backward == next);
		dprintf("27");
		next->l.backward->l.forward = next->l.forward;
		dprintf("28");
		next->l.forward->l.backward = next->l.backward;
		dprintf("29");
		f->h.size += next->h.size;
		dprintf("30");
		
		dprintf("31");
		next = FREE(((char *)f) + f->h.size);
	}
	
	dprintf("32");
	assert(next->h.size < 0);	//ensure next buffer really is free
	
	dprintf("33");
	next->h.prev = f->h.size;
	
	return;
}

void KiAddMemoryToKernelPool(void *buf, size_t len)
{
	struct freehead *f = FREE(buf);
	struct head *next;
	
	assert(len - sizeof(struct head) <= ~((size_t)EndS + 1));	//ensure we're not overflowing
	
	f->h.prev = 0;
	
	//add to freelist
	assert(kfreelist.l.backward->l.forward == &kfreelist);
	assert(kfreelist.l.forward->l.backward == &kfreelist);
	f->l.forward = &kfreelist;
	f->l.backward = kfreelist.l.backward;
	kfreelist.l.backward = f;
	f->l.backward->l.forward = f;
	
	len -= sizeof(struct head);		//subtract overhead
	f->h.size = (size_t)len;		//set size in header
	next = HEAD(((char *)f) + len);		//*next = *f - struct head (e.g. we have room for it)
	next->prev = (size_t)len;		//previous (to next) is new
	next->size = EndS;			//set size to EndS - this means that this is the end
	
	ktotal_memory += len;
	
	return;
}

void KiGetKernelMemStats(struct KiMemStats *ms)
{
	struct freehead *f = kfreelist.l.forward;
	
	ms->NumAlloc = (size_t)knumalloc;
	ms->NumFree = (size_t)knumfree;
	ms->CurAlloc = (size_t)ktotal_alloc;
	ms->TotalMemory = (size_t)ktotal_memory;
	ms->TotalFree = 0;
	ms->MaxFreeBlk = -1;
	while(f != &kfreelist)
	{
		assert(f->h.size > 0);
		ms->TotalFree += (size_t)f->h.size;
		if(f->h.size > ms->MaxFreeBlk)
			ms->MaxFreeBlk = (size_t)f->h.size;
		f = f->l.forward;
	}
	
	return;
}

int KiGetNumAlloc(void)
{
	return knumalloc;
}

void KiDumpPool(void *buf)
{
	struct freehead *f = FREE(buf);
	
	while(f->h.size != EndS)
	{
		size_t size = f->h.size;
		
		if(size < 0)
		{
			size = -size;
			printf("Allocated buffer: size %6ld bytes.\n", (long)size);
		} else {
			char *err = "";
			
			assert(size > 0);
			if((f->l.backward->l.forward != f) || (f->l.forward->l.backward != f))
				err = "  (Bad free list links)";
			printf("Free block:       size %6ld bytes.%s\n", (long)size, err);
		}
		f = FREE(((char *)f) + size);
	}
}

void KiDumpFreeStruct(struct freehead *fh)
{
	printf("\n h.prev = %0i \n h.size = %0i \n backward = %08X \n current = %08X\n forward = %08X\n", fh->h.prev, fh->h.size, fh->l.backward, fh, fh->l.forward);
	return;
}
